package org.example.algorithm.dp;

import java.util.Arrays;

public class MinPathSumSolution {

    //dp[i][j] = Math.min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])
    //特殊情况i=0,j=0
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        int[][] dp = new int[row][column];
        for (int i=0;i<row;i++) {
            for (int j=0;j<column;j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[i][j];
                } else if(i == 0) {
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                } else if(j == 0) {
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]);
                }
            }
        }
        return dp[row-1][column-1];
    }

    //记忆化搜索
    public int minPathSum2(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] mem = new int[row][col];
        for (int i=0;i<row;i++) {
            Arrays.fill(mem[i], -1);
        }
        dfs(row-1, col-1, grid, mem);
        return mem[row-1][col-1];
    }

    private int dfs(int row, int col, int[][] grid, int[][] mem) {
        if (row <0 || col<0) {
            return Integer.MAX_VALUE;
        }
        if (row == 0 && col == 0) {
            return mem[row][col] = grid[row][col];
        }
        if (mem[row][col] != -1) {
            return mem[row][col];
        }
        return mem[row][col] = Math.min(dfs(row-1, col, grid, mem), dfs(row, col-1, grid, mem)) + grid[row][col];
    }
}
